import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Set;

/**
 * This class will represent a modified linear probing hash table. 
 * The modification is specified in the comments for the put method.
 */
public class HashTable<K,V> {

	/**
	 * Constant determining the max load factor
	 */
	private final double MAX_LOAD_FACTOR = 0.71;

	/**
	 * Constant determining the initial table size
	 */
	private final int INITIAL_TABLE_SIZE = 11;

	/**
	 * Number of elements in the table
	 */
	private int size;

	/**
	 * The backing array of this hash table
	 */
	private MapEntry<K,V>[] table;

	private int table_length;

	/**
	 * Initialize the instance variables
	 * Initialize the backing array to the initial size given
	 */
	@SuppressWarnings("unchecked")
	public HashTable() {
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0;		
		table_length = INITIAL_TABLE_SIZE;
	}

	/**
	 * Add the key value pair in the form of a MapEntry
	 * Use the default hash code function for hashing
	 * This is a linear probing hash table so put the entry in the table accordingly
	 * 
	 * Make sure to use the given max load factor for resizing
	 * Also, resize by doubling and adding one. In other words:
	 * 
	 * newSize = (oldSize * 2) + 1
	 *
	 * The load factor should never exceed maxLoadFactor at any point. So if adding this element
	 * will cause the load factor to be exceeded, you should resize BEFORE adding it. Otherwise
	 * do not resize.
	 * 
	 * IMPORTANT Modification: If the given key already exists in the table
	 * then set it as the next entry for the already existing key. This means
	 * that you will never be replacing values in the hashtable, only adding or removing.
	 * This is similar to external chaining
	 * 
	 * @param key This will never be null
	 * @param value This can be null
	 */

	@SuppressWarnings("unchecked")
	public void put(K key,V value){
		boolean exist = false;
		size++;
		MapEntry<K,V> mapEntry = new MapEntry<K,V>(key,value);
		int index = getIndex(key);

		if (table[index]!=null && key.equals(table[index].getKey())) {  //75
			exist = true;}
		else
			for (int i=0;i<table_length;i++)
				if (table[i]!=null && key.equals(table[i].getKey())) {   //79
					exist = true;
					index=i;}

		if (exist) {   // if key already exists			
			MapEntry<K,V> entry = table[index];
			while (entry.getNext()!=null)
				entry = entry.getNext();
			entry.setNext(mapEntry);}

		else {   // if the key does not exist
			if (size> (MAX_LOAD_FACTOR*table_length)) {  // resize table
				MapEntry<K,V>[] temp = table;
				int temp_length = table_length;
				table_length = table_length*2+1; 
				table = new MapEntry[table_length];
				size=1;
				for (int i=0;i<temp_length;i++) 
					if (temp[i]!=null)
						if (!temp[i].isRemoved())
							put(temp[i].getKey(),temp[i].getValue());
			} 

			boolean yes = true;
			if (table[getIndex(key)]==null)  // when table[index] is empty
				table[getIndex(key)] = mapEntry;
			else if (key.equals(table[getIndex(key)].getKey()) && table[getIndex(key)].getNext()==null 
					&& table[getIndex(key)].isRemoved())  // if same key exists at index but isRemoved 
				table[getIndex(key)].setNext(mapEntry);
			else if (!key.equals(table[getIndex(key)].getKey()) && table[getIndex(key)].getNext()==null 
					&& table[getIndex(key)].isRemoved()) // if different key exists at index but isRemoved
				table[getIndex(key)] = mapEntry;
			else {	// when different key exists at index and is NOT removed... search for next open spot
				for (int i=getIndex(key);i<table_length;i++)
					if (table[i]==null){
						table[i] = mapEntry;
						yes = false;
						break;}
				if (yes)
					for (int i=0;i<getIndex(key);i++)
						if (table[i]==null){
							table[i] = mapEntry;
							break;}
			}

		}
	}

	private int getIndex(K key) {
		return  Math.abs(key.hashCode() % table_length);
	}

	/**
	 * Remove the entry with the given key.
	 * 
	 * If there are multiple entries with the same key then remove the last one
	 * 
	 * @param key
	 * @return The value associated with the key removed
	 */
	public V remove(K key) {
		boolean exist = false;
		V removed = null;

		int index = getIndex(key);
		if (table[index]!=null && key.equals(table[index].getKey())) 
			exist = true;
		else
			for (int i=0;i<table_length;i++) 				
				if (table[i]!=null && key.equals(table[i].getKey())) {
					exist = true;
					index=i;}

		if (exist) {   // if key exists
			if (table[index].getNext()==null) {   // if there are one entry with the key 
				removed = table[index].getValue();
				table[index].setRemoved(true);}
			else {   // if there are multiple entries with the same key
				MapEntry<K,V> entry = table[index];
				while (entry.getNext().getNext()!=null)
					entry = entry.getNext();				
				removed = entry.getNext().getValue();
				entry.setNext(null);}}
		if (removed!=null)
			size--;
		return removed;

	}

	/**
	 * Checks whether an entry with the given key exists in the hash table
	 * 
	 * @param key
	 * @return
	 */
	public boolean contains(K key) {
		if (keyValues(key)>0) return true;
		return false; }

	/**
	 * Return a collection of all the values
	 * 
	 * We recommend using an ArrayList here
	 *
	 * @return 
	 */
	public Collection<V> values(){
		Collection<V> collection = new ArrayList<V>();

		for (int i=0;i<table_length;i++)
			if (table[i]!=null && table[i].getKey()!=null)
				if (!table[i].isRemoved()){
					MapEntry<K,V> entry = table[i];
					collection.add(table[i].getValue());
					while (entry.getNext()!=null) {
						collection.add(entry.getValue());
						entry = entry.getNext();}
				}
		return collection; }

	/**
	 * Return a set of all the distinct keys
	 * 
	 * We recommend using a HashSet here
	 * 
	 * Note that the map can contain multiple entries with the same key
	 * 
	 * @return
	 */
	public Set<K> keySet(){
		Collection<K> collection = new HashSet<K>();

		for (int i=0;i<table_length;i++)
			if (table[i]!=null && table[i].getKey()!=null)
				if (!table[i].isRemoved())
					collection.add(table[i].getKey());
		Set<K> set = new HashSet<K>(collection);
		return set;	}

	/**
	 * Return the number of values associated with one key
	 * Return -1 if the key does not exist in this table
	 * @param key
	 * @return
	 */	
	public int keyValues(K key){
		int count = 0;

		int index = getIndex(key);
		if (table[index]!=null &&  key.equals(table[index].getKey()))
			if (!table[index].isRemoved()){				MapEntry<K,V> entry = table[index];				while (entry.getNext()!=null) {					entry = entry.getNext();					count++; }				return count+1; }
		return -1; }

	/**
	 * Return a set of all the unique key-value entries
	 * 
	 * Note that two map entries with both the same key and value
	 * could exist in the map.
	 * 
	 * @return
	 */
	public Set<MapEntry<K,V>> entrySet() {
		Set<MapEntry<K,V>> collection = new HashSet<MapEntry<K,V>>();
		for (int i=0;i<table_length;i++)
			if (table[i]!=null && table[i].getKey()!=null) {
				MapEntry<K,V> entry = table[i];
				if (!entry.isRemoved()){
					collection.add(entry);
					while (entry.getNext()!=null) {						
						entry = entry.getNext();
						collection.add(entry);}
				}
			}


		return collection;	}

	/**
	 * Clears the hash table
	 */
	@SuppressWarnings("unchecked")
	public void clear() {
		table = new MapEntry[INITIAL_TABLE_SIZE];
		size = 0; }

	/*
	 * The following methods will be used for grading purposes do not modify them
	 */

	public int size() {
		return size; }

	public void setSize(int size) {
		this.size = size; }

	public MapEntry<K,V>[] getTable() {
		return table; }

	public void setTable(MapEntry<K,V>[] table) {
		this.table = table; }


	public String toString(){

		String answer = new String("[");
		for(int i=0; i<table_length;i++){
			V value;
			if(table[i]!=null){
				value = table[i].getValue();
			}
			else{
				value = null;
			}
			if(i==table_length-1){
				answer+=value + "]";
				break;
			}
			if(value!=null) answer+= value + ", ";
			else{
				answer+= "null, ";
			}
		}
		return answer;
	}

}